minimum spanning trees (MST) can be maps of nodes and edges such that a
single path
is calculated that all nodes lie on and such that the total length of the
path is
at (or near) a minimum value.

Almost all MSTs are two-dimensional - useful for network designs that
eliminate
loops, vehicle routing problems that minimize fuel costs, integrated circuit
design, etc.

kruskal's algorithm is one method of genrating a MST (prim's algorithm is
another one)

I wrote a script that generates a MST pov code object file - using a
modified version
of kruskal for speed improvements and to produce three dimensional trees..

Inputs to the script are number of nodes, ranges for each of x,y,z
coordinates.

Attached are simple examples of the output.

The first image has the range for the z coordinates deliberately
flattened to a value of zero - shows a 2D MST.

The second image is a 3D MST without z flattening.

Both images employ 256 nodes.

The pov script has spheres for the nodes and
cylinders for the edges.
(Of course any arbitrary objects could be substituted
 for spehere|cyclinder.)
These images are meant just to demonstrate  MSTs.

I'm going to experiment with various things as nodes and edges.
Suggestions are welcome.
First idea is a reticule of crystals.

Question: I had doubts about nodes|edges not intersecting
via this method so I wrapped the object file with intersection { }.
Since nothing rendered I assume this means there are no
intersections of objects.
Is this a fair assumption?
Obviously, sphere radii and cylinder radii can radically modify
possible intersections.

pan

Post a reply to this message

Attachments:
Download 'kruskal_02.png' (134 KB) Download 'kruskal_01.png' (95 KB)

Preview of image 'kruskal_02.png'

Preview of image 'kruskal_01.png'